package core;

public class FordFulkerson {

	public static MaxFlowSolver getSolver() {
		return new MaxFlowSolver() {
			public double solve(SimpleGraph the_graph) {
				return new FordFulkerson().getMaxFlow(the_graph);
			}
			public String getName() {return "Ford Fulkerson";}
		};
	}

	public double getMaxFlow(SimpleGraph graph) {
		double maxFlow = 0;
		// Initate a flow graph with edges having capacity >= delta
		FlowGraph flowGraph = new FlowGraph(graph);

		// find s-t path
		flowGraph.unVisitEdges();
		Path path = SearchPath.getPath(flowGraph, flowGraph.getSource(), flowGraph.getSink(), new Path(), 0);
		
		while(path.size() > 0) {
			// if path found agument path
			maxFlow += flowGraph.augment(path);
			flowGraph.unVisitEdges();
			path = SearchPath.getPath(flowGraph, flowGraph.getSource(), flowGraph.getSink(), new Path(), 0);
		}
		System.out.println(flowGraph);

		return maxFlow;
	}
	
	public static void main(String[] args) throws Exception {
		SimpleGraph graph;
		graph = new SimpleGraph();
		GraphInput.LoadSimpleGraph(graph, args[0]);
		FordFulkerson fordFulkerson = new FordFulkerson();
		double maxFlow = fordFulkerson.getMaxFlow(graph);
		System.out.println("Final: " + maxFlow);
	}
}
